package 二叉树;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import com.mj.printer.BinaryTreeInfo;

public class BinarySearchTree<E> implements BinaryTreeInfo {
	public static abstract class Visitor<E> {
		private boolean stop;

		public abstract boolean visitor(E element);
	}

	// 二叉树节点内部类
	private static class Node<E> {
		E element;
		Node<E> leftNode;
		Node<E> rightNode;
		Node<E> parentNode;

		@SuppressWarnings({ "unchecked" })
		public Node(E element, @SuppressWarnings("rawtypes") Node parent) {
			this.element = element;
			this.parentNode = parent;
		}

		@SuppressWarnings("unused")
		public boolean isLeafNode() {
			return leftNode == null && rightNode == leftNode;
		}

		public boolean hasTwoChilden() {
			return leftNode != null && rightNode != null;
		}
	}

	// 节点数量
	private int size;
	// 根节点
	private Node<E> rootNode;
	// 比较器(构建二叉树规则)
	private Comparator<E> compareComparator;

	// 构造方法,比较器由E来实现
	public BinarySearchTree() {
		this(null);
	}

	// 构造方法,比较器由外界传递
	public BinarySearchTree(Comparator<E> comparator) {
		this.compareComparator = comparator;
	}

	// 返回节点数量
	public int size() {
		return size;
	}

	// 返回是否是空树
	public boolean isEmpty() {
		return size == 0;
	}

	// 清空二叉树
	public void clear() {
		rootNode = null;
		size = 0;
	}

	// 添加节点
	public void add(E element) {
		// 检查添加元素
		elementNoNullCheck(element);

		// 添加root节点
		if (rootNode == null) {
			rootNode = new Node<>(element, null);
			size++;
			return;
		}

		// 添加的不是根节点
		// 找到父节点
		Node<E> node = rootNode;
		Node<E> parentNode = rootNode;
		int cmp = 0;
		do {
			cmp = compare(element, node.element);
			parentNode = node;
			if (cmp > 0) {
				node = node.rightNode;
			} else if (cmp < 0) {
				node = node.leftNode;
			} else {
				node.element = element;
				return;
			}

		} while (node != null);

		// 插入到父节点中
		Node<E> newNode = new Node<>(element, parentNode);
		if (cmp > 0) {
			parentNode.rightNode = newNode;
		} else {
			parentNode.leftNode = newNode;
		}
		size++;
	}

	// 删除某个元素的节点
	public void remove(E element) {
		remove(node(element));
	}

	// 判断是否包含某个节点元素的节点
	public boolean contains(E elementE) {
		return node(elementE) != null;
	}

	private void remove(Node<E> node) {
		if (node == null) {
			return;
		}

		size--;

		if (node.hasTwoChilden()) { // 当前节点有两个子节点
			// 找到前驱/后继节点:
			// 01.将前驱/后继节点的赋值到当前节点
			// 02.删除前驱/后继节点
			Node<E> successorNode = successor(node);
			node.element = successorNode.element;
			// 将当前节点标记到后继节点位置,后续做删除操作.
			node = successorNode;
		}

		// 删除node节点（node的度必然是1或者0）
		Node<E> replacementNode = node.leftNode != null ? node.leftNode : node.rightNode;

		// node拥有左子节点/右子节点,为度为1的节点.
		if (replacementNode != null) {
			// 更改parent
			replacementNode.parentNode = node.parentNode;
			if (node.parentNode == null) { // node为根节点
				rootNode = replacementNode;
			} else {
				// node是父节点的左子节点,那么就讲父节点的左子节点替换为当前节点的子节点.
				if (node == node.parentNode.leftNode) {
					node.parentNode.leftNode = replacementNode;
				} else {
					node.parentNode.rightNode = replacementNode;
				}
			}
			// 下面的判断代表node为度为0的叶子节点.
		} else if (node.parentNode == null) { // node是叶子节点并且是根节点
			rootNode = null;
		} else { // node是叶子节点，但不是根节点
			// node是父节点的左子节点,那么就将父节点的左子节点置为null
			if (node == node.parentNode.leftNode) {
				node.parentNode.leftNode = null;
			} else {
				node.parentNode.rightNode = null;
			}
		}
	}

	// 寻找node的前驱节点(中序遍历时的前一个节点)
	@SuppressWarnings("unused")
	private Node<E> predecessor(Node<E> node) {
		if (node == null) {
			return null;
		}

		// 如果node有左子节点,那么前驱节点一定在左子节点开始一直往右找
		Node<E> pNode = node.leftNode;
		if (pNode != null) {
			while (pNode.rightNode != null) {
				pNode = pNode.rightNode;
			}
			return pNode;
		}

		// node没有左子节点,就从它的父/祖父节点中寻找
		while (node.parentNode != null && node == node.parentNode.leftNode) {
			node = node.parentNode;
		}

		return node.parentNode;
	}

	// 寻找node的后继节点(中序遍历时的后一个节点)
	private Node<E> successor(Node<E> node) {
		if (node == null) {
			return null;
		}

		// 如果node有右子节点,那么后继节点一定在右子节点开始一直往左找
		Node<E> pNode = node.rightNode;
		if (pNode.rightNode != null) {
			while (pNode.leftNode != null) {
				pNode = pNode.leftNode;
			}
			return pNode;
		}

		// node没有右子节点,就从它的父/祖父节点中寻找
		while (node.parentNode != null && node == node.parentNode.rightNode) {
			node = node.parentNode;
		}

		return node.parentNode;
	}

	// 根据元素查找节点
	private Node<E> node(E element) {
		Node<E> node = rootNode;
		while (node != null) {
			int cmp = compare(node.element, element);
			if (cmp == 0) {
				return node;
			} else if (cmp > 0) {
				node = node.leftNode;
			} else {
				node = node.rightNode;
			}
		}
		return null;
	}

	// 检查元素是否为空值
	private void elementNoNullCheck(E element) {
		if (element == null) {
			throw new IllegalArgumentException("element can not be null");
		}
	}

	// 比较器
	@SuppressWarnings("unchecked")
	private int compare(E elementOne, E elementTwo) {
		if (compareComparator != null) {
			return compareComparator.compare(elementOne, elementTwo);
		}
		return ((Comparable<E>) elementOne).compareTo(elementTwo);
	}

	// 前序遍历
	public void preorderTraversal() {
		preorderTraversal(rootNode);
	}

	private void preorderTraversal(Node<E> node) {
		if (node == null) {
			return;
		}

		System.out.println(node.element);
		preorderTraversal(node.leftNode);
		preorderTraversal(node.rightNode);
	}

	// 中序遍历
	public void inorderTraversal() {
		inorderTraversal(rootNode);
	}

	private void inorderTraversal(Node<E> node) {
		if (node == null) {
			return;
		}

		inorderTraversal(node.leftNode);
		System.out.println(node.element);
		inorderTraversal(node.rightNode);
	}

	// 后序遍历
	public void postorderTraversal() {
		postorderTraversal(rootNode);
	}

	private void postorderTraversal(Node<E> node) {
		if (node == null) {
			return;
		}

		postorderTraversal(node.leftNode);
		postorderTraversal(node.rightNode);
		System.out.println(node.element);
	}

	// 层序遍历
	public void levelOrderTraversal() {
		if (rootNode == null) {
			return;
		}

		Queue<Node<E>> queue = new LinkedList<>();
		// 先将根节点入队
		queue.offer(rootNode);

		// 然后出队的时候依次将左右节点入队
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			System.out.println(node.element);

			if (node.leftNode != null) {
				queue.offer(node.leftNode);
			}

			if (node.rightNode != null) {
				queue.offer(node.rightNode);
			}
		}
	}

	// 遍历停止由外界告知.
	public void preorder(Visitor<E> visitor) {
		if (visitor == null) {
			return;
		}
		preorder(rootNode, visitor);
	}

	private void preorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) {
			return;
		}
		visitor.stop = visitor.visitor(node.element);
		preorder(node.leftNode, visitor);
		preorder(node.rightNode, visitor);
	}

	// 中序遍历
	public void inorder(Visitor<E> visitor) {
		if (visitor == null) {
			return;
		}
		inorder(rootNode, visitor);
	}

	private void inorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) {
			return;
		}
		inorder(node.leftNode, visitor);
		if (visitor.stop) {
			return;
		}
		visitor.stop = visitor.visitor(node.element);
		inorder(node.rightNode, visitor);
	}

	// 后序遍历
	public void postorder(Visitor<E> visitor) {
		if (visitor == null) {
			return;
		}
		postorder(rootNode, visitor);
	}

	private void postorder(Node<E> node, Visitor<E> visitor) {
		if (node == null || visitor.stop) {
			return;
		}

		postorder(node.leftNode, visitor);
		postorder(node.rightNode, visitor);
		if (visitor.stop) {
			return;
		}
		visitor.stop = visitor.visitor(node.element);
	}

	// 层序遍历
	public void levelOrder(Visitor<E> visitor) {
		if (rootNode == null || visitor == null) {
			return;
		}

		Queue<Node<E>> queue = new LinkedList<BinarySearchTree.Node<E>>();
		queue.offer(rootNode);
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			
			if (visitor.visitor(node.element)) {
				return;
			} 
			
			if (node.leftNode != null) {
				queue.offer(node.leftNode);
			}
			
			if (node.rightNode != null) {
				queue.offer(node.rightNode);
			}	
		}
	}
	
	// 获取二叉树的高度
	public int height() {
		return height(rootNode);
	}
	
	private int height(Node<E> node) {
		if (node == null) {
			return 0;
		}
		Queue<Node<E>> queue = new LinkedList<BinarySearchTree.Node<E>>();
		queue.offer(node);
		// 树的高度
		int height = 0;
		// 一层节点数量
		int levelSize = 1;
		while (!queue.isEmpty()) {
			Node<E> node2 = queue.poll();
			levelSize--;
			
			if (node2.leftNode != null) {
				queue.offer(node2.leftNode);
			}
			
			if (node2.rightNode != null) {
				queue.offer(node2.rightNode);
			}
			
			if (levelSize == 0) {
				levelSize = queue.size();
				height ++;
			}
		}
		
		return height;
	}
	
	public String toString() {
		StringBuilder sBuilder = new StringBuilder();
		toString(rootNode, sBuilder, "");
		return sBuilder.toString();
	}
	
	private void toString(Node<E> node, StringBuilder sBuilder, String prefix) {
		if (node == null) {
			return ;
		}
		toString(node.leftNode, sBuilder, "L---");
		sBuilder.append(prefix).append(node.element).append("\n");
		toString(node.rightNode, sBuilder, "R---");
	}
	
	// 是否是完全二叉树
	public Boolean isComplete() {
		if (rootNode == null) {
			return false;
		}
		Queue<Node<E>> queue = new LinkedList<BinarySearchTree.Node<E>>();
		queue.offer(rootNode);
		Boolean isLeaf = false;
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			if (isLeaf && node.isLeafNode()) {
				return false;
			}
			
			if (node.leftNode != null) {
				queue.offer(node.leftNode);
			} else if (node.rightNode != null) {
				return false;
			}
			
			if (node.rightNode != null) {
				queue.offer(node.rightNode);
			} else {
				isLeaf = true;
			}
		}
		return true;
	}

	public Object root() {
		return rootNode;
	}

	@SuppressWarnings("unchecked")
	public Object left(Object node) {
		return ((Node<E>) node).leftNode;
	}

	@SuppressWarnings("unchecked")
	public Object right(Object node) {
		return ((Node<E>) node).rightNode;
	}

	public Object string(Object node) {
		@SuppressWarnings("unchecked")
		Node<E> myNode = (Node<E>) node;
		String parentString = "null";
		if (myNode.parentNode != null) {
			parentString = myNode.parentNode.element.toString();
		}
		return myNode.element + "(" + parentString + ")";
	}

}
